#include <stdio.h>
#include <stdbool.h>

#define MEM_SIZE 8096
#define MIN_BLOCK_SIZE 48

//在内存块的起始存放块信息 Block大小为24B=8+8+8
typedef struct Block {
    size_t size;
    bool free;
    struct Block *next;
} Block;

static char mem[MEM_SIZE];//内存
static Block *head = NULL;

//初始化内存
void initMem() {
    head = (Block *) mem;
    head->size = MEM_SIZE - sizeof(Block);
    head->free = true;
    head->next = NULL;
}

void split_block(Block *b, size_t size) {
    Block *new_block = (Block *) ((char *) b + sizeof(Block) + size);
    new_block->size = b->size - size - sizeof(Block);
    new_block->free = true;
    new_block->next = b->next;
    b->size = size;
    b->free = false;
    b->next = new_block;
}

//分配大小为size的内存，地址放在result
void *umalloc(size_t size) {
    Block *current, *prev;
    void *result = NULL;

    if (!head) {
        initMem();
    }
    //遍历链表，寻找可以分配的块
    current = head;
    while (current && !(current->free && current->size >= size)) {
        prev = current;
        current = current->next;
    }
    //如果可以分配
    if (current) {
        //判断是否可以分裂
        if (current->size > size + sizeof(Block) + MIN_BLOCK_SIZE) {
            split_block(current, size);
        }
        current->free = false;
        result = (void *) (++current);
    }
    return result;
}

//释放内存，ptr为地址
void ufree(void *ptr) {
    if (ptr) {
        Block *block = (Block *) ((char *) ptr - sizeof(Block));//向前sizeof(Block)字节获得block的位置
        block->free = true;
    }
}

//遍历链表，将可合并的内存块合并
void umerge() {
    Block *current, *prev;
    current = head;
    while (current && current->next) {
        //空闲区块合并
        if (current->free && current->next->free) {
            current->size += sizeof(Block) + current->next->size;
            current->next = current->next->next;
        } else {
            prev = current;
            current = current->next;
        }
    }
}

int main() {
    printf("为int型变量分配空间\n");
    int *a = umalloc(sizeof(int));
    Block *blka = (Block *) ((char *) a - sizeof(Block));
    printf("分配信息：size:%zu,free:%d\n", blka->size, blka->free);

    printf("链表：");
    for (Block *p = head; p != NULL; p = p->next) {
        printf("[size:%zu,free:%d]-->", p->size, p->free);
    }
    printf("NULL\n");

    printf("释放空间\n");
    ufree(a);

    printf("链表：");
    for (Block *p = head; p != NULL; p = p->next) {
        printf("[size:%zu,free:%d]-->", p->size, p->free);
    }
    printf("NULL\n");

    printf("整理\n");
    umerge();
    printf("链表：");
    for (Block *p = head; p != NULL; p = p->next) {
        printf("[size:%zu,free:%d]-->", p->size, p->free);
    }
    printf("NULL\n");


    return 0;
}
